package training;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_5_13_Training {
    //找出所有子集的异或总和再求和
    int sum = 0;
    public int subsetXORSum(int[] nums) {
        dfs1(nums,0,0);
        return sum;
    }

    public void dfs1(int[] nums,int index,int path){
        if(index==nums.length){
            sum += path;
            return ;
        }
        int val1 = path^nums[index];
        int val2 = path;
        dfs1(nums,index+1,val1);
        dfs1(nums,index+1,val2);
    }

    //电话号码的字母组合
    String[] string;
    List<String> ret;
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        if(digits.length()==0){
            return ret;
        }
        string = new String[10];
        string[2] = "abc"; string[3] = "def"; string[4] = "ghi"; string[5] = "jkl"; string[6] = "mno";
        string[7] = "pqrs"; string[8] = "tuv"; string[9] = "wxyz";
        dfs2(digits,0,new StringBuffer(""));
        return ret;
    }

    public void dfs2(String digits,int pos,StringBuffer path){
       if(pos == digits.length()){
           ret.add(path.toString());
           return ;
       }
        String val = string[digits.charAt(pos) - '0'];
        for (int i = 0; i < val.length(); i++) {
            path.append(val.charAt(i));
            dfs2(digits,pos+1,new StringBuffer(path));
            path.deleteCharAt(path.length()-1);

        }
    }

    //括号生成
    List<String> retString;
    StringBuffer path;
    public List<String> generateParenthesis(int n) {
        retString = new ArrayList<>();
        path = new StringBuffer();
        dfs3(n,0,n*2);
        return retString;
    }

    public void dfs3(int n, int m,int size){
        if(path.length() == size){
            retString.add(path.toString());
            return;
        }
        if(n>0){
            path.append('(');
            dfs3(n-1,m+1,size);
            path.deleteCharAt(path.length()-1);
        }
        if(m>0){
            path.append(')');
            dfs3(n,m-1,size);
            path.deleteCharAt(path.length()-1);
        }
    }

    //组合
    List<List<Integer>> list;
    List<Integer> listpath;
    public List<List<Integer>> combine(int n, int k) {
        list = new ArrayList<>();
        listpath = new ArrayList<>();
        dfs(n,k,0);
        return list;
    }

    public void dfs(int n,int k,int pos){
        if(listpath.size() == k){
            list.add(new ArrayList<>(listpath));
            return ;
        }
        for (int i = pos; i <= n; i++) {
            listpath.add(i);
            dfs(n,k,i+1);
            listpath.remove(listpath.size()-1);
        }
    }

//    public static void main(String[] args) {
//        System.out.println(8^0);
//    }
}
